package leetcode_BFS;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 地图分析
 * <p>算法: 多源 BFS</p>
 *
 * @author yezh
 * @date 2023/8/14 16:57
 */
public class _1162 {

    public int maxDistance(int[][] grid) {
        // BFS 可以求最短距离
        int ans = -1, n = grid.length;
        Deque<int[]> queue = new LinkedList<>();
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    queue.offer(new int[]{i, j});
                    grid[i][j] = 0;
                }
                // 标记是否被访问
                else grid[i][j] = -1;
            }
        while (!queue.isEmpty()) {
            int len = queue.size();
            while (len-- > 0) {
                int[] poll = queue.poll();
                int r = poll[0], c = poll[1], dis = grid[r][c] + 1;
                boolean flag = false;
                if (r + 1 < n && grid[r + 1][c] == -1) {
                    grid[r + 1][c] = dis;
                    flag = true;
                    queue.offer(new int[]{r + 1, c});
                }
                if (r - 1 >= 0 && grid[r - 1][c] == -1) {
                    grid[r - 1][c] = dis;
                    flag = true;
                    queue.offer(new int[]{r - 1, c});
                }
                if (c + 1 < n && grid[r][c + 1] == -1) {
                    grid[r][c + 1] = dis;
                    flag = true;
                    queue.offer(new int[]{r, c + 1});
                }
                if (c - 1 >= 0 && grid[r][c - 1] == -1) {
                    grid[r][c - 1] = dis;
                    flag = true;
                    queue.offer(new int[]{r, c - 1});
                }
                if (flag) ans = Math.max(ans, dis);
            }
        }
        return ans;
    }

}
